ACP avec noyau

Plan

• Motivation
• ACP avec noyau
• Fonction noyau
• Application pratique
• Discussion

Motivation

• L’ACP reduit la dimention tout en conservant le maximum de variance dans les données.
• Premières composante les plus informatives.
• Information non linéaire pas facile à capturer

Exemple

Exemple

Exemple

Autre exemple

Autre exemple

Soit la transformation

\[\Phi(\textbf{x}) = (x^2, \sqrt{2}xy, y^2).\] En appliquant cette transformation sur les données originales, on obtient un problème linéaire.

Autre exemple

Autre exemple

Rappel de l’ACP

Mathématiquement, les composantes principales sont obtenues selon une décomposition par valeurs et vecteurs propres de la matrice de covariances

\[ \frac{1}{N} \sum_{i = 1}^{N} \textbf{x}_i\textbf{x}_i^T.\] Correspond à la meilleure projection des données dans une dimension réduite.

ACP avec noyau

On applique une ACP sur les données projetées (Schölkopf, Smola, and Müller 1997). On décompose la matrice de covariances de la matrice des transformations non linéaires

\[ \frac{1}{N} \sum_{i = 1}^{N} \Phi(\textbf{x}_i)\Phi(\textbf{x}_i)^T = \frac{1}{N} \sum_{i = 1}^{N} \textrm{k}(\textrm{x}_i, \textrm{x}_i) .\]

Transformation quadratique

Pour une données à deux attributs \(\textrm{x} = (x_1, x_2)\), on applique la transformation \(\Phi(\textbf{x}) = (x_1^2, \sqrt{2}x_1x_2, x_2^2)\). Le produit scalaire devient

\[ \begin{aligned} (\Phi(\textbf{x}_i) \cdot \Phi(\textbf{x}_j)) &= (x_{i, 1}^2 + \sqrt{2} x_{i, 1} x_{i, 2} + x_{i, 2}^2)(x_{j, 1}^2 + \sqrt{2} x_{j, 1} x_{j, 2} + x_{j, 2}^2)^T\\ &= ((x_{i, 1}x_{i, 2})(x_{j, 1}x_{j, 2})^T)^2\\ &= (\textbf{x}_i \cdot \textbf{x}_j)^2. \end{aligned} \]

On remarque qu’on n’a pas besoin de calculer les valeurs \(x_1^2, \sqrt{2}x_1x_2\) ou \(x_2^2\).

Projection dans un autre espace d’attributs

-En général, on projète les données \(\textbf{x}\) dans un espace d’attributs par une transformation non linéaire.

-Formellement, on a

\[ \begin{aligned} \Phi: \mathbb{R}^N &\to \mathcal{F}\\ \textbf{x} &\mapsto \Phi(\textbf{x}) \end{aligned} \]

• Au lieu de faire l’apprentissage statistique sur \(\textbf{x}_1, \textbf{x}_2, \dots, \textbf{x}_N\), on le fait sur \(\Phi(\textbf{x}_1), \Phi(\textbf{x}_2), \dots, \Phi(\textbf{x}_N)\).

Fonction noyau

• Pour l’ACP avec noyau, on a seulement besoin du produit scalaire
• \(\Phi\) peut être une fonction non définie ou de dimension infinie, tant que son produit scalaire existe.
• Soit \[k(\textrm{x}, \textrm{y}) = \Phi(\textrm{x})\cdot \Phi(\textrm{y}).\] Alors, on peut écrire la matrice de covariance de \(\Phi\) comme

\[\frac{1}{N} \sum_{i = 1}^{N} \Phi(\textbf{x}_i) \Phi(\textbf{x}_i)^T = \frac{1}{N} \sum_{i = 1}^{N} \textrm{k}(\textrm{x}_i, \textrm{x}_i).\]

Transformation polynomiale

Pour le polynome multinomial, on a

\[\Phi(\textrm{x}) = \sum_{\textbf{J} \in \{0, 1, \dots, N\}} w_{\textrm{J}} \prod_{i = 1}^{k}x_{J_i}.\] Ce vecteur contient les données toutes les combinaisons polynomiales de dimension \(k\). Par exemple,

\[x_1^k, x_2^k, \dots, x_p^k,\] \[x_1, x_1^2,\dots, x_1^{k-1}, x_1^{k},\] \[x_1^{k-1}x_2, x_1^{k-2}x_2^2, \dots, x_1 x_2^{k-1},\] \[x_1^{k-1}x_2, x_1^{k-1}x_3, \dots, x_1^{k-1}x_p\]

Transformation polynomiale

La transformation produit des données dans une dimension\((p + 1)^k\). Par contre, on peut montrer que

\[\Phi(\textrm{x})\cdot \Phi(\textrm{y}) = (1 + \textrm{x}\cdot \textrm{y})^k = \textrm{k}(\textrm{x}, \textrm{y}).\]

Transformation gaussienne

Soit la transformation

\[\Phi_k(\textrm{x}) = \frac{1}{\sqrt{k!}}e^{-\frac{||\textrm{x}||^2}{2}}\prod_{i = 1}^N\frac{x_{J_i}}{\sigma} .\]

On considère l’espace d’attributs de toutes les combinaisons de \(\Phi_k(\textrm{x}), k\in \mathbb{N}\).

Alors, on a

\[\Phi(\textrm{x})\cdot \Phi(\textrm{y}) = e^{-\frac{||\textrm{x} - \textrm{y}||^2}{2\sigma^2}} = \textrm{k}(\textrm{x}, \textrm{y}).\]

Normalisation des données

• La formule \[\frac{1}{N} \sum_{i = 1}^{N} \textrm{k}(\textrm{x}, \textrm{x})\] est valide si les données sont centrées, c-à-d que \[\sum_{i = 1}^{N} \Phi(\textrm{x}_i) = 0.\]

• Si \(\Phi(\textrm{x})\) est de dimension infinie, il est impossible de vérifier cette hypothèse.

Normalisation des données

La solution est proposée par (Schölkopf, Smola, and Müller 1997)

Soit \[K_{ij} = (k(\textbf{x}_i, \textbf{x}_j))_{ij} \textrm{ et } K,\]

la matrice des \(K_{ij}\). Alors, on peut centrer la matrice \(\tilde{K}\) selon

\[\tilde{K}_{ij} = (K - 1_NK - K1_N + 1_NK1_N)_{ij}\]

où \((1_N)_{ij} := \frac{1}{N}\) et éviter de calculer les données \(\Phi(\textbf{x})\).

Lien avec le SVM

Rappel : On veut maximiser \(M\) tel que \[y_i(\beta_0 + \beta_1 x_{i1} \dots + \beta_p x_{ip}) \geq M(1 - \varepsilon_i) ~ \forall ~ i = 1, \dots, n\] sous les contraintes \[ \begin{aligned} \sum_{j= 0}^p\beta_j^2 &= 1\\ \varepsilon_i &\geq 0 ~\forall~i\\ \sum_{i = 1}^n\varepsilon_i &\leq c \end{aligned} \]

Classifieur à vecteurs de support : formulation duale avec marges douces

Avec les multiplicateurs de Lagrange, la fonction à maximiser devient

\[-\frac{1}{2} \sum_{t = 1}^n\sum_{s = 1}^n \alpha_t\alpha_s r_tr_s\textbf{x}_t\textbf{x}_s^T + \sum_{t = 1}^n \alpha_t\] sous les contraintes

\[ \begin{aligned} \sum_{t= 1}^n\alpha_tr_t &= 0\\ 0\leq \alpha_i &\leq c ~\forall~i\\ \end{aligned} \]

Applications MNIST

On applique l’ACP avec noyau sur le jeu de données MNIST (LeCun et al. 1998).

Applications MNIST

Discussion

Avantages

• Découvrir les relations non linéaires entre les données
• Possiblement réduire davantage la dimension
• Noyau = truc utile lorsque seulement le produit scalaire est requis
• Succès dans détection de visages (K. I. Kim, Jung, and Kim 2002)

Discussion

Incovénients

• Ajuster les hyper-paramètres
• Non-supervisé : l’ajustement des hyper-paramètres peut être compliqué
• Ne permet pas de reconstruire les données